'''
https://leetcode.cn/problems/search-in-rotated-sorted-array/?envType=study-plan-v2&envId=top-interview-150
'''
import bisect
from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if len(nums) == 1:
            return 0 if nums[0] == target else -1
        l, r = 0, len(nums) - 1
        k = 0
        if nums[0] > nums[-1]:
            # 二分找到峰值点,
            #   1)v[m] < v[-1]: k在左侧
            #       else: k可能在正确的区间,可以动 l
            #   2)  在1)的条件下 v[l]一定 < v[m], 动l
            while l <= r:
                mid = l + r >> 1
                if nums[mid] > nums[mid+1]:
                    k = mid
                    break
                elif nums[mid] < nums[-1]:
                    r = mid - 1
                else:
                    l = mid + 1
        p1 = bisect.bisect_left(nums, target, 0, k)
        p2 = bisect.bisect_left(nums, target, k+1, len(nums)-1)
        if nums[p1] == target:
            return p1
        elif nums[p2] == target:
            return p2
        else:
            return -1

nums = [4,5,6,7,0,1,2]
# nums = [2,4,5,6,7,0,1]
# nums = [7,8,1,2,3,4,5,6]
target = 0
print(Solution().search(nums, target))